|
In theoretical computer science, in particular in the theory of formal languages, useless rules of a formal grammar are those rules of symbol production that are unreachable or unproductive, that is, that can or need never be applied. ==Definition== Given a context-free grammar, a nonterminal symbol ''X'' is called productive, or generating, if there is a derivation ''X'' ⇒ * ''w'' for some string ''w'' of terminal symbols. A nonterminal symbol ''X'' is called reachable if there is a derivation ''S'' ⇒ * α''X''β for some strings α, β of non-terminal and terminal symbols, and where ''S'' denotes the grammar's start symbol. A rule with an unproductive or unreachable symbol on its left-hand side can be deleted from the grammar without changing the accepted (a.k.a. generated) language. Likewise, an alternative containing such a symbol can be deleted from the right-hand side of a rule without changing the language. Such rules and alternatives are called useless.〔; here: Sect.7.1.1, p.256〕 For formal grammars that are not context-free, similar definitions apply. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Useless rules」の詳細全文を読む スポンサード リンク
|